package com.javaDemo.ti;

import java.util.Arrays;

/**
 * 回溯算法实现 - 单词搜索问题
 * 
 * @ClassName: Huisufa
 * @Auther: csy
 * @Date: 2020/6/7 17:13
 * @Description: 实现了经典的回溯算法，用于解决二维网格中的单词搜索问题
 * 
 *               问题描述：
 *               给定一个二维网格和一个单词，找出该单词是否存在于网格中。
 *               单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中"相邻"
 *               指的是水平或垂直方向上相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * 
 *               算法思想：
 *               1. 回溯算法是一种通过探索所有可能的候选解来找出所有解的算法
 *               2. 如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化来舍弃该解
 *               3. 在单词搜索问题中，我们从网格的每个单元格开始，尝试按照单词的字母顺序进行深度优先搜索
 *               4. 使用visited数组标记已访问的单元格，防止重复使用
 * 
 *               时间复杂度：O(M*N*4^L)，其中M和N是网格的长宽，L是单词长度，4是四个方向
 *               空间复杂度：O(M*N)，主要是visited数组的空间
 * 
 *               参考：https://leetcode-cn.com/problems/word-search/solution/zai-er-wei-ping-mian-shang-shi-yong-hui-su-fa-pyth/
 */
public class Huisufa {

    /**
     * 定义四个方向：上、左、右、下
     * 每个方向由一个坐标偏移量表示：{行偏移, 列偏移}
     */
    private static final int[][] DIRECTIONS = { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };

    // 网格的行数
    private static int rows;
    // 网格的列数
    private static int cols;
    // 目标单词的长度
    private static int len;
    // 标记已访问的单元格
    private static boolean[][] visited;
    // 目标单词转换为字符数组
    private static char[] charArray;
    // 示例二维网格
    private static char[][] board = {
            { 'A', 'B', 'C', 'E' },
            { 'S', 'F', 'C', 'S' },
            { 'A', 'D', 'E', 'E' }
    };

    /**
     * 主方法：用于测试回溯算法解决单词搜索问题
     * 
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        // 测试用例1：存在的单词
        String word1 = "SEE";
        System.out.println("测试用例1：");
        System.out.println("二维网格：");
        printBoard(board);
        System.out.println("查找单词：" + word1);
        System.out.println("查找结果：" + (exist(board, word1) ? "找到了" : "未找到"));

        // 测试用例2：不存在的单词
        String word2 = "ABCB";
        System.out.println("\n测试用例2：");
        System.out.println("二维网格：");
        printBoard(board);
        System.out.println("查找单词：" + word2);
        System.out.println("查找结果：" + (exist(board, word2) ? "找到了" : "未找到"));

        // 测试用例3：边界情况 - 单个字符
        String word3 = "A";
        System.out.println("\n测试用例3：");
        System.out.println("二维网格：");
        printBoard(board);
        System.out.println("查找单词：" + word3);
        System.out.println("查找结果：" + (exist(board, word3) ? "找到了" : "未找到"));
    }

    /**
     * 辅助方法：打印二维网格
     * 
     * @param board 二维网格
     */
    private static void printBoard(char[][] board) {
        for (char[] row : board) {
            System.out.println(Arrays.toString(row));
        }
    }

    /**
     * 判断单词是否存在于二维网格中
     * 
     * 算法步骤：
     * 1. 初始化全局变量
     * 2. 从网格的每个单元格开始，尝试进行深度优先搜索
     * 3. 如果从任意一个单元格出发能找到单词，返回true
     * 4. 如果所有单元格都尝试过仍未找到，返回false
     *
     * @param board 二维字符网格
     * @param word  要查找的单词
     * @return 如果单词存在于网格中返回true，否则返回false
     */
    public static boolean exist(char[][] board, String word) {
        // 初始化行数
        rows = board.length;
        // 处理空网格的情况
        if (rows == 0) {
            return false;
        }
        // 初始化列数
        cols = board[0].length;
        // 初始化访问标记数组
        visited = new boolean[rows][cols];

        // 初始化单词长度和字符数组
        len = word.length();
        charArray = word.toCharArray();

        // 从网格的每个单元格开始尝试查找
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                // 如果从当前单元格出发能找到单词，返回true
                if (dfs(i, j, 0)) {
                    return true;
                }
            }
        }
        // 所有单元格都尝试过仍未找到，返回false
        return false;
    }

    /**
     * 深度优先搜索（DFS）实现回溯算法的核心逻辑
     * 
     * 算法步骤：
     * 1. 检查当前字符是否匹配
     * 2. 如果是最后一个字符且匹配，返回true
     * 3. 如果不是最后一个字符但匹配，标记当前单元格为已访问
     * 4. 向四个方向继续搜索下一个字符
     * 5. 如果任何方向能找到剩余的字符，返回true
     * 6. 否则回溯：将当前单元格标记为未访问，返回false
     *
     * @param x     当前单元格的行索引
     * @param y     当前单元格的列索引
     * @param begin 当前要匹配的字符在word中的索引
     * @return 如果从当前单元格出发能找到剩余的字符返回true，否则返回false
     */
    private static boolean dfs(int x, int y, int begin) {
        // 如果已经到达单词的最后一个字符，只需检查当前单元格是否匹配
        if (begin == len - 1) {
            return board[x][y] == charArray[begin];
        }

        // 检查当前单元格是否匹配当前字符
        if (board[x][y] == charArray[begin]) {
            // 标记当前单元格为已访问
            visited[x][y] = true;

            // 向四个方向继续搜索
            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];

                // 检查新位置是否在网格范围内且未被访问
                if (inArea(newX, newY) && !visited[newX][newY]) {
                    // 如果从新位置能找到剩余的字符，返回true
                    if (dfs(newX, newY, begin + 1)) {
                        return true;
                    }
                }
            }

            // 回溯：将当前单元格标记为未访问
            visited[x][y] = false;
        }

        // 当前路径无法找到单词，返回false
        return false;
    }

    /**
     * 检查坐标是否在网格范围内
     *
     * @param x 行索引
     * @param y 列索引
     * @return 如果坐标在网格范围内返回true，否则返回false
     */
    private static boolean inArea(int x, int y) {
        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}
